In processing data, particularly data relating to visual images for example, many systems include filters for suppressing undesirable noise components of the image data, while enhancing characteristics of the data representing significant features of the image. One example of such filters is a median filter. A median filter enhances trend changes and suppresses small-scale variations in image data. A paper entitled "Fast Computing Median Filters On General-Purpose Image Processing Systems", authored by Urs E. Ruttimann and Richard L. Webber, which appeared in Optical Engineering, (SPIE), Sept., 1986, Volume 25, No. 9, pages 1064 through 1067, and a paper entitled "A Fast Method for Real-Time Median Filtering" by E. Ataman, in the IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-28, No. 4, Aug. 1980 at page 415, are believed to summarize state-of-the-art embodiments of median-like filters using general-purpose image processing systems, such as The National Bureau of Standards PIPE system. Such median filters require generally n comparison operations for each n.times.1 (1-dimensional) window due to the necessity of rank-sorting of the data items. As will be shown below, the present invention requires only two comparisons per window, for one-dimensional processing, no matter what the size of the one-dimensional window. For two-dimensional windows of n.times.n data items, median filters implemented by rank-sorting require on the order of n-squared operations, in general. In such cases, the present invention provides a filter system also requiring only on the order of n comparison operations.
In Arai, et al. U.S. Pat. No. 4,298,895, noise is eliminated from digitally recorded visual image data by first determining the proportion of picture elements (pixels) in an area surrounding an objective area having a first visual level or component, and then assigning the same visual level or component to the objective area when the proportion is above a predetermined value, thereby providing a majority filter for binary images. More specifically, in this prior system, image levels are binary, and are assigned one bit per pixel. If the binary values of pixels surrounding a pixel being processed are summed together, and exceed a predetermined threshold value, the pixel being processed is assigned a value of 1. Accordingly, this prior system represents a one-bit fixed-neighborhood majority filter for binary images. As a result, the method disclosed is inapplicable for processing gray-scale image data.
Unlike Arai, the present invention involves creating a local histogram, rather than a simple count. Arai uses threshold comparisons for pixel selection, whereas in the present invention selection is based on histogram bin comparison.
In Sternberg U.S. Pat. No. 4,301,443, an image analyzer system is disclosed for analyzing image patterns comprised of a matrix of points each representing a multi-bit digital electrical signal. A chain of identical serial neighborhood transformation stages is included, with each stage including a plurality of input lines for forming an input data bus, with each line carrying a particular digital data bit. Each stage includes an analysis circuit for analyzing the digitized image patterns. A central controller is used to operate selector circuitry for selecting particular bits of data to be analyzed by each stage in processing the image data.
Frankle, et al. U.S. Pat. No. 4,384,336 teaches a system for calculating an approximation of visual properties of objects. The system optimizes imaging data for use in particular display media such as photography, television and printing. Lightness fields are produced from multiple comparisons between information associated with different segmental areas of a given image field. Different groups of the segmental areas are utilized in making the comparisons, wherein the different groupings have at least one spatial parameter different from other of the groupings. The comparisons are made in a predetermined sequence, and employ the results of prior comparisons.
In Delman U.S. Pat. No. 4,513,440, a median filter is disclosed for processing high resolution image data, including gray-scale data. Gray-scale image pixels are rank-sorted in a neighborhood by bit-serial pipeline processing. The hardware median filter disclosed provides output imagery similar to the present invention, but functions differently and uses different hardware than the present invention.
In Lougheed U.S. Pat. No. 4,541,116, an image filter for providing neighborhood image processing is disclosed. The values of neighboring pixels in an image are compared with the value of a given pixel within the group. The comparison results are combined for forming a vector to address a programmable look-up table. A selector is controlled by the output of the look-up table for either maintaining the value of a pixel being processed, or changing the value of the pixel into the value of a neighboring pixel, the latter value having been ranked in a predetermined order by a rank sorter providing comparison of the values of pixels within a given neighborhood. In other words, median filtering is provided via pairwise comparisons of neighboring pixels, which are passed through the look-up table in a sorting operation.
In Fox et al U.S. Pat. No. 4,554,593, an image-processing system is disclosed for reproducing on a bi-level median documents having mixed formats, such as text, half-tone, and continuous tone, via selective thresholding of scan PEL values derived from the characteristics of the image material to be reproduced. The PEL values are selectively applied to one of a plurality of threshold devices for thresholding a predetermined format, including symmetry discrimination in conjunction with an information homogeneity discriminator for eliminating local anomalies.
Higgans U.S. Pat. No. 4,625,330, discloses a system for enhancing analog video pulses. Binary OCR image data is converted to gray-scale data via the video system. The converted data is then scaled to 3-bits to reduce combinatoric searching requirements for determining all likely acceptance or rejection patterns of selected neighbors. Accepted patterns are provided as binary output signals.
In relation to the above-mentioned prior art references, the present invention is a significant improvement in that no rank-sorting of data is required. In general, each prior art patent is based on a particular sorting method requiring serial, bitwise, or pairwise comparators, or table lookup. Such methods require increasing amounts of hardware and lower speeds as the size of the window increases. In contrast, the present invention requires no extra hardware or slowdown for arbitrarily large windows for one-dimensional windows. For two-dimensional windows, the prior art requires extra hardware and processing speed reductions at least proportional to the number of pixels in the window. For the plurality filter embodiment of the present invention, the proportion is the "front porch" on the advancing window, a much smaller number than that of prior art. For a window consisting of k rows by k columns, n=k.sup.2 and the front porch consists of k=.sqroot.n pixels. Similarly, for a window of h rows by k columns, the front porch consists of h pixels. The current window technique in which a reduced precision histogram is applied to a local window in the present invention is unique and more efficient compared to prior art.